# 构建堆
def heap(nums: list[int]) -> list[int]:
    h, i = [0], 0
    for x in nums:
        i += 1
        h.append(x)
        k = i
        while k > 1 and h[k] > h[k // 2]:
            h[k], h[k // 2] = h[k // 2], h[k]
            k //= 2
    return h

# 堆排序
def heapSort(h: list[int]) -> list[int]:
    print('堆排序开始:')
    n, step = len(h) - 1, 1
    for k in range(n, 1, -1):
        i = 1
        h[i], h[k] = h[k], h[i]
        while i < k:
            j = i * 2
            if j + 1 < k and h[j + 1] > h[j]: 
                j += 1
            if j < k and h[j] > h[i]:
                h[i], h[j] = h[j], h[i]
                i = j
            else: break
        print('第%d步:' % step, h[1:])
        step += 1
    return h

# 演示：构建堆然后进行堆排序
nums = [ 24, 61, 7, 92, 4, 6, 44 ]
print('原数组:', nums)

# 构建堆
h = heap(nums)
print('构建出来的堆为:', h[1:])

# 堆排序
h = heapSort(h)
print('最终堆排序结果为:', h[1:])
